#include <iostream>
#include <vector>
#include <assert.h>

#include "TestCaseGenerator.h"

using namespace std;

void Swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

void MergeSortWithIndex(vector<int> &array, int startIdx, int endIdx)
{
	if (endIdx - startIdx <= 0)
		return;

	int middleIdx = (startIdx + endIdx) >> 1;
	MergeSortWithIndex(array, startIdx, middleIdx);
	MergeSortWithIndex(array, middleIdx + 1, endIdx);

	vector<int> tmpVec;
	int frontIdx = startIdx;
	int backIdx = middleIdx + 1;

	while (frontIdx <= middleIdx && backIdx <= endIdx)
	{
		if (array[frontIdx] <= array[backIdx])
			tmpVec.push_back(array[frontIdx++]);
		else
			tmpVec.push_back(array[backIdx++]);
			
	}
	if (frontIdx <= middleIdx)
	{
		while (frontIdx <= middleIdx)
			tmpVec.push_back(array[frontIdx++]);
	}
	if (backIdx <= endIdx)
	{
		while (backIdx <= endIdx)
			tmpVec.push_back(array[backIdx++]);
	}

	assert(tmpVec.size() == endIdx - startIdx + 1);
	for (int i = startIdx; i <= endIdx; i++)
	{
		array[i] = tmpVec[i - startIdx];
	}
}


void MergeSort(vector<int> &array)
{
	if (array.size() < 2)
		return;

	int length = array.size();
	MergeSortWithIndex(array, 0, length - 1);
}


int main()
{
	shared_ptr<TestCaseGenerator> tcgPtr;

	vector<int> testCaseArray = tcgPtr->GenerateTestCase(5, 0, 10);
	cout << "TestCaseArray before sort: " << endl;
	for each (int var in testCaseArray)
		cout << var << " ";
	cout << endl;
	MergeSort(testCaseArray);
	cout << "TestCaseArray after sort: " << endl;
	for each (int var in testCaseArray)
		cout << var << " ";
	cout << endl;

	vector<int> testCaseArray1 = tcgPtr->GenerateTestCase();
	cout << "TestCaseArray1 before sort: " << endl;
	for each (int var in testCaseArray1)
		cout << var << " ";
	cout << endl;
	MergeSort(testCaseArray1);
	cout << "TestCaseArray1 after sort: " << endl;
	for each (int var in testCaseArray1)
		cout << var << " ";
	cout << endl;

	return 0;
}